package DynamicProgramming;

import java.math.BigDecimal;

public class _62_UniquePaths {
    //solution 1:using recursion
    //time limited exceeded
    public int uniquePaths0(int m, int n) {
        return getEveryPath(0, 0, m, n);
    }

    public int getEveryPath(int horizontal, int vertical, int m, int n) {
        if (horizontal >= n || vertical >= m) {
            return 0;
        }
        if (horizontal == n - 1 && vertical == m - 1) {
            return 1;
        }
        return getEveryPath(horizontal + 1, vertical, m, n) + getEveryPath(horizontal, vertical + 1, m, n);
    }

    //solution 2:using math permutation method
    //hint:the total path is A(m-1)*(n-1),the duplicate path is A(m-1)*(n-1),so just use the total paths to divide the duplicate path
    public int uniquePaths1(int m, int n) {
        BigDecimal total = new BigDecimal(1);
        for (int i = 2; i <=m+n-2 ; i++) {
            total = total.multiply(new BigDecimal(i));
        }
        BigDecimal dupliVertical = new BigDecimal(1);
        BigDecimal dupliHorizental = new BigDecimal(1);
        for (int i = 2; i <= m-1 ; i++) {
            dupliVertical = dupliVertical.multiply(new BigDecimal(i));
        }
        for (double i = 2; i <= n - 1; i++) {
            dupliHorizental = dupliHorizental.multiply(new BigDecimal(i));
        }
        return(total.divide(dupliVertical.multiply(dupliHorizental))).intValue();
    }

    //solution 3:solution 2's update
    //hint: in fact,assume m is bigger,A(m-1)*(n-1)/A(m-1)*(n-1) equals to (m+n-2)*…(m)/(A(n-1)),so simplify solution 2's calculation
    public int uniquePaths(int m, int n) {
        int max = Math.max(m, n);
        int min = Math.min(m, n);
        long total = 1;
        for(int i=1;i<min;i++,max++) {
            total = total * max / i;
        }
        return (int)total;
    }

}
